"""
主体思想是使深度优先遍历去寻找所有的潜在环路
"""

import numpy as np
from functools import cmp_to_key

f = open('/data/test_data.txt')
m = {}

# 数据预处理，提出转账源id和目的id,并将目标id加入源id的列表中
for data in f.readlines():
    l_data = data.split(',')
    id1, id2 = int(l_data[0]), int(l_data[1])
    m.setdefault(id1, []).append(id2)

f.close()
res = []   # 结果列表


def dfs(to_ids, path):
    """
    深度优先遍历
    :param to_ids: path中最后一个元素会转账的id列表
    :param path: 访问路径
    :return: 无
    """
    if len(path) > 7:                       # 长度大于7，剔除
        return
    for to_id in to_ids:                    # 逐个访问下一个要转账的id
        if to_id not in m:                  # 剪枝，避免重复访问
            continue
        if to_id in path[1:]:               # 剪枝，避免重复访问
            continue
        elif to_id == path[0]:              # 判断是否回到原点
            if len(path) <= 2:              # 不要路径小于3的
                return
            sorted_path = my_sort(path)     # 对路径进行排序，使得开始值为路径中最小
            if sorted_path not in res:      # 可能会重复，比如[197,56,18]也是一个环路，但是排序后和[18, 197, 56]一样
                res.append(sorted_path)     # 加入结果
            return
        else:                               # 下一步深度搜索
            new_path = path + [to_id]
            dfs(m[to_id], new_path)


def my_sort(path):
    """
    将路径重新排一下
    使得在一个环路的路径中，起始值是该环路的最小值
    :param path: 输入一个构成环路的id列表
    :return: 排序好的
    """
    flag, min_value = -1, np.inf

    for key, value in enumerate(path):
        if value < min_value:
            flag, min_value = key, value
    return path[flag:] + path[:flag]


def comp(val1, val2):
    """
    排序使用的比较函数
    :param val1:
    :param val2:
    :return:
    """
    if len(val1) != len(val2):
        return len(val1) < len(val2)

    for key, v1 in enumerate(val1):
        if v1 == val2[key]:
            continue
        elif v1 < val2[key]:
            return -1
        else:
            return 1
    return 0


if __name__ == '__main__':
    for k in m:
        dfs(m[k], [k])
    res.sort(key=len)                   # 先按长度排序
    res.sort(key=cmp_to_key(comp))      # 在使用自己的比较方法排序
    f = open('/projects/student/result.txt', 'w')
    str_res = []
    str_res.append(str(len(res))+"\n")
    for v in res:
        c = map(str, v)                 # 将整数元素全部转换为字符串类型
        temp = ",".join(c)              # 用,连接起来
        temp += "\n"
        str_res.append(temp)
    f.writelines(str_res)               # 按行写入
    f.close()
    # print(str_res)
    # print(res)
